Selection Sort এবং Insertion Sort হল দুটি সহজ এবং মৌলিক সর্টিং অ্যালগরিদম। উভয়ই সাধারণত শিক্ষার উদ্দেশ্যে ব্যবহৃত হয় এবং ছোট ডেটা সেটের জন্য কার্যকরী।
১. Selection Sort
১.১ Selection Sort এর ধারণা
Selection Sort হল একটি সর্টিং অ্যালগরিদম যা প্রতিটি ধাপে সর্বনিম্ন (বা সর্বাধিক) উপাদানকে খুঁজে বের করে এবং সেটিকে প্রথম অবস্থানে স্থাপন করে। এটি n সংখ্যক ধাপে কাজ করে, যেখানে প্রতিটি ধাপে একটি ন্যূনতম উপাদান খোঁজা হয়।
১.২ C প্রোগ্রামে Selection Sort উদাহরণ
#include <stdio.h>
// Function to perform Selection Sort
void selectionSort(int arr[], int size) {
for (int i = 0; i < size - 1; i++) {
int minIndex = i; // Assume the minimum is the first element
for (int j = i + 1; j < size; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j; // Update minIndex if a smaller element is found
}
}
// Swap the found minimum element with the first element
int temp = arr[minIndex];
arr[minIndex] = arr[i];
arr[i] = temp;
}
}
int main() {
int arr[] = {64, 25, 12, 22, 11};
int size = sizeof(arr) / sizeof(arr[0]);
selectionSort(arr, size);
printf("Sorted array: \n");
for (int i = 0; i < size; i++) {
printf("%d ", arr[i]);
}
printf("\n");
return 0;
}
১.৩ Selection Sort এর বিশ্লেষণ
Worst Case Time Complexity: O(n²)
(সবচেয়ে খারাপ ক্ষেত্রে, প্রতিটি উপাদানের জন্য পুরো তালিকাটি অনুসন্ধান করতে হয়।)
Best Case Time Complexity: O(n²)
(এটি কোন ভাল পরিস্থিতিতে উন্নতি করে না, কারণ প্রতিটি উপাদানকে পরীক্ষা করতে হয়।)
Average Case Time Complexity: O(n²)
(গড় ক্ষেত্রে, আবার n² তুলনা করতে হয়।)
Space Complexity: O(1)
(এই অ্যালগরিদম স্থান সঞ্চয় করে, কারণ এটি ইনপুট অ্যারে ছাড়া অতিরিক্ত স্থান ব্যবহার করে না।)
২. Insertion Sort
২.১ Insertion Sort এর ধারণা
Insertion Sort হল একটি সর্টিং অ্যালগরিদম যা একটি তালিকার উপাদানগুলোকে একটি সাজানো অংশে একে একে যুক্ত করে। এটি কার্যকরভাবে কাজ করে এবং বিশেষ করে ছোট ডেটা সেটের জন্য খুব কার্যকরী।
২.২ C প্রোগ্রামে Insertion Sort উদাহরণ
#include <stdio.h>
// Function to perform Insertion Sort
void insertionSort(int arr[], int size) {
for (int i = 1; i < size; i++) {
int key = arr[i];
int j = i - 1;
// Move elements of arr[0..i-1], that are greater than key, to one position ahead
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j = j - 1;
}
arr[j + 1] = key; // Insert key at the correct position
}
}
int main() {
int arr[] = {12, 11, 13, 5, 6};
int size = sizeof(arr) / sizeof(arr[0]);
insertionSort(arr, size);
printf("Sorted array: \n");
for (int i = 0; i < size; i++) {
printf("%d ", arr[i]);
}
printf("\n");
return 0;
}
২.৩ Insertion Sort এর বিশ্লেষণ
Worst Case Time Complexity: O(n²)
(যখন তালিকা পুরোপুরি বিপরীত ক্রমে সাজানো থাকে।)
Best Case Time Complexity: O(n)
(যখন তালিকা ইতিমধ্যেই সাজানো থাকে।)
Average Case Time Complexity: O(n²)
(গড় ক্ষেত্রে, এটি প্রায় n² তুলনা করতে হয়।)
Space Complexity: O(1)
(Insertion Sort স্থান সঞ্চয় করে, কারণ এটি ইনপুট অ্যারে ছাড়া অতিরিক্ত স্থান ব্যবহার করে না।)
৩. Selection Sort এবং Insertion Sort এর তুলনা
| বৈশিষ্ট্য | Selection Sort | Insertion Sort |
|---|---|---|
| Time Complexity | O(n²) | O(n²) (Worst) / O(n) (Best) |
| Space Complexity | O(1) | O(1) |
| Stable | না (Unstable) | হ্যাঁ (Stable) |
| Best for | ছোট ডেটা সেট | ইতিমধ্যেই সাজানো তালিকা |
| Swap Count | অনেক বেশি | কম |
Read more
